# 给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
#  请返回所有可行解 s 中最长长度。
#
#  示例 1：
#  输入：arr = ["un","iq","ue"]
# 输出：4
# 解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
#
#  示例 2：
#  输入：arr = ["cha","r","act","ers"]
# 输出：6
# 解释：可能的解答有 "chaers" 和 "acters"。
#
#  示例 3：
#  输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
# 输出：26
import collections
from typing import List


class Solution:
    def maxLength2(self, arr: List[str]) -> int:
        """
        使用数字优化空间
        由于只关心某个字符是否出现，而不关心某个字符在原字符串的位置，因此可以将字符串使用 int 进行表示(低26位中为1的表示对应的小写字符在该字符串中)
        :param arr:
        :return:
        """
        filtered = []
        res = 0
        def getNoRepeativeStrs() -> None:  # 去重,并将有重复字符的字符串过滤掉
            for s in arr:
                tmp = 0
                for ch in s:
                    idx = ord(ch) - ord("a")
                    if ((tmp >> idx) & 1):  # // 若 tmp 已有 ch，则说明 s 含有重复字母，无法构成可行解
                        tmp = 0
                        break
                    tmp |= 1 << idx  # 将字符对应的位置置为1(将字符加入到用位图表示的字符串中)
                if tmp > 0:
                    filtered.append(tmp)

        def backtrace(pos: int, tmpStr: int) -> None:
            if pos == len(filtered):
                nonlocal res
                res = max(res, bin(tmpStr).count("1"))
                return
            if (tmpStr & filtered[pos]) == 0:  # 只有当前结果字符串(tmpStr)和需要尝试的字符串不存在重复字符串才需要将其加入
                backtrace(pos + 1, tmpStr | filtered[pos])
            backtrace(pos + 1, tmpStr)  # 也可以不选当前遍历的字符串(得到的结果可能更大)

        getNoRepeativeStrs()
        backtrace(0, 0)
        return res

    def maxLength1(self, arr: List[str]) -> int:
        """
        先将所给字符串进行去重，并将有重复字符的字符串都过滤掉
        然后在经过过滤的字符串数组中使用回溯法进行尝试，获得最大长度
        :param arr:
        :return:
        """
        res = 0
        def backTrace(pos: int, tmpStr: str) -> None:
            nonlocal res
            if pos == len(noRepeativeStrs):
                res = max(res, len(tmpStr))
                return
            if not hasRepeative(noRepeativeStrs[pos], tmpStr):  # 只有当前结果字符串(tmpStr)和需要尝试的字符串不存在重复字符串才需要将其加入
                backTrace(pos + 1, tmpStr + noRepeativeStrs[pos])
            backTrace(pos + 1, tmpStr)  # 也可以不选当前遍历的字符串

        def hasRepeative(str1: str, str2: str) -> bool:
            return max(collections.Counter(str1 + str2).values()) >= 2

        def getNoRepeativeStrs() -> List[str]:
            resStrs = []
            for w in arr:
                tmp = [0] * 26
                flag = True
                for s in w:
                    index = ord(s) - 97
                    if tmp[index] >= 1:
                        flag = False
                        break
                    else:
                        tmp[index] = 1
                if flag:
                    resStrs.append(w)
            return resStrs

        noRepeativeStrs = getNoRepeativeStrs()
        backTrace(0, '')
        return res

    def maxLength(self, arr: List[str]) -> int:
        return self.maxLength2(arr)


if __name__ == "__main__":
    arr = ["un", "iq", "ue"]
    arr = ["cha", "r", "act", "ers"]
    arr = ["abcdefghijklmnopqrstuvwxyz"]
    # arr = ["aa", "bb"]
    print(Solution().maxLength(arr))
